#include<string.h>
#include<stdlib.h>
int getMaximumGenerated(int n)
{
    if (n == 0 || n == 1)
        return n;

    int *nums = (int *)malloc(sizeof(int) * (n + 1));
    memset(nums, 0, sizeof(int) * (n + 1));
    nums[0] = 0;
    nums[1] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (2 * i <= n)
        {
            nums[2 * i] = nums[i];
        }

        if (2 * i <= n - 1)
        {
            nums[2 * i + 1] = nums[i] + nums[i + 1];
        }
    }

    int max = nums[0];
    for (int i = 1; i <= n; i++)
    {
        if (nums[i] > max)
            max = nums[i];
    }

    return max;
}
